import java.util.*;

 class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }



public class BinarySearchTreeIterator {

    Stack<TreeNode> stack = new Stack<TreeNode>();
    
    public BinarySearchTreeIterator(TreeNode root) {
        TreeNode p = root;

        while(p!=null){
            stack.push(p);
            p=p.left;
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if(stack.size()==0)
            return false;

        return true;
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode p = stack.pop();

        TreeNode currentNode = p.right;

        while(currentNode!=null){
            stack.push(currentNode);
            currentNode = currentNode.left;
        }

        return p.val;
    }

    
    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        TreeNode n1 = new TreeNode(5);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(1);
        TreeNode n4 = new TreeNode(3);
        TreeNode n5 = new TreeNode(8);

        root.left = n1;
        n1.left = n2;
        n1.right = n5;
        n2.left = n3;
        n2.right = n4;
        
        BinarySearchTreeIterator b = new BinarySearchTreeIterator(root);

        while(b.hasNext()){
            System.out.println(b.next());
        }
    }
}
